BOJ20198 Papričice

풀이

트리의 간선을 두 개 잘라서 세 개의 트리로 나눌때, 제일 큰 트리와 제일 작은 트리의 차이를 최소화하는 문제입니다. 표기의 편의상 임의의 정점, 여기서는 1번정점을 루트로 만들어주고, 서브트리 x의 크기를 S[x], x의 부모노드를 p[x]라고 합시다. 'dfs(x)=한 트리가 subtree of x일때의 최솟값'이라는 정의로 dfs를 하면, 즉 x와 p[x]를 자르고 나머지 한 간선은 parent쪽 subtree에서 자를 때 최솟값을 구해보도록 합시다. 이제 parent쪽 서브트리의 임의의 노드y에서 p[y]로 가는 간선을 하나 더 제거해서 나오는 두 subtree의 크기를 분석해봅시다. 다음과 같이 두 개의 케이스로 나누어서 보면 편합니다.

1. Y가 x의 ancestor인 경우: y쪽 컴포넌트 크기는 S[y]-S[x]이고 P[y]쪽 컴포넌트 크기는 N-S[y]입니다. S[x]는 고정이고, 최대와 최소의 차이를 줄이기 위해서는 S[y]-S[x]와 N-S[y]의 값이 최대한 비슷해져야 합니다. S[y]-S[x]=N-S[y]로 두고 변수S[y]에 대해 정리하면 S[y]=(S[x]+N)/2 이므로 해당 값에 제일 가까운 y를 고르면 최적입니다.

2. Y가 x의 ancestor가 아닌경우: Y쪽 컴포넌트 크기는 S[y]이고, P[y]쪽 컴포넌트 크기는 N-S[x]-S[y]입니다. S[x]는 고정이고, 최대와 최소의 차이를 줄이기 위해서는 S[y]와 N-S[x]-S[y]의 값이 최대한 비슷해져야 합니다. S[y]=N-S[x]-S[y]로 두고 변수 S[y]에 대해 정리하면 S[y]=(N-S[x])/2이므로 해당 값에 제일 가까운 y를 고르면 최적입니다.

모든 dfs(x)에서 두가지 경우 각각에대해 가장 가까운 값을 구할 수 있는 자료구조를 잘 관리해주면 문제를 해결할 수 있습니다. 1번 경우는 multiset으로 쉽게 관리할 수 있지만, 2번 경우는 생각보다 어렵습니다. 그래서 다음과 같은 관찰이 추가적으로 필요합니다. 2번 케이스의 경우

root\

LCA(x,y)

subtree(x)/ \subtree(y)

이러한 형태인데, x를 고정하고 답을 구하는것과 y를 고정하고 답을 구하는것은 동일한 것을 알 수 있습니다. 그런데, y를 고정하면 x의 dfs order가 더 빠르면서 y의 ancestor가 아니기 때문에 dfs가 종료된 상태입니다. 따라서 그냥 dfs(x)하면서 종료될 때마다 x의 값을 2번 케이스용 multiset에 추가해주면, x고정시에 y케이스는 처리되지 않지만, y를 고정해두고 계산할때 처리되기 때문에 문제가 없습니다. 이제 문제를 해결할 수 있습니다! 코드: http://boj.kr/5bc0e5da8e7747e880830c263f454982